/*
 * Graph.cpp
 *
 *  Created on: 11 lis 2013
 *      Author: dawid.wysakowicz
 */

#include "Graph.hpp"
#include <limits>
#include <algorithm>
#include "Common.hpp"

using common::Matrix;

namespace algorithm
{

Graph::Graph(size_t verticesCount, size_t source, size_t target) :
		source_(source), target_(target), maxFlow_(0), capacity_(verticesCount,
				verticesCount)
{
}

bool Graph::bfs(const size_t matrixSize, const size_t startingVertex,
		const Matrix<int>& flows, std::vector<int>& path,
		std::vector<int>& residual, std::queue<size_t>& q)
{
	for (size_t i = 0; i < matrixSize; ++i)
	{
		int residualCapacity = capacity_(startingVertex, i)
				- flows(startingVertex, i);
		if (residualCapacity == 0 || path[i] != -1)
		{
			continue;
		}

		path[i] = startingVertex;
		residual[i] = std::min(residual[startingVertex], residualCapacity);

		if (i == target_)
		{
			return true;
		}

		q.push(i);
	}

	return false;
}

uint32_t Graph::getMaxFlow()
{
	return maxFlow_;
}

void Graph::load(const std::vector<std::tuple<int, int, int> >& edges)
{
	std::for_each(edges.begin(), edges.end(),
			[this] (std::tuple<int, int, int> triplet)
			{this->capacity_(std::get<0>(triplet), std::get<1>(triplet)) = std::get<2>(triplet);});
}

void Graph::extendFlow(const std::vector<int>& residual,
		const std::vector<int>& path, Matrix<int>& flows)
{
	maxFlow_ += residual[target_];
	size_t vertex = target_;
	size_t nextVertex;
	do
	{
		nextVertex = path[vertex];
		flows(nextVertex, vertex) += residual[target_];
		flows(vertex, nextVertex) -= residual[target_];
		vertex = nextVertex;
	} while (nextVertex != source_);
}

Matrix<int> Graph::calculate()
{
	const size_t matrixSize = capacity_.rowsSize();
	Matrix<int> flows(matrixSize, matrixSize);

	std::queue<size_t> q;
	q.push(source_);

	std::vector<int> path(matrixSize, -1);

	std::vector<int> residual(matrixSize, 0);
	residual[source_] = std::numeric_limits<int>::max();

	while (!q.empty())
	{
		size_t x = q.front();
		q.pop();

		bool targetFound = bfs(matrixSize, x, flows, path, residual, q);

		if (targetFound)
		{
			extendFlow(residual, path, flows);
			while (!q.empty())
			{
				q.pop();
			}
			q.push(source_);
			std::replace_if(path.begin(), path.end(), predicates::const_true<int>, -1);
			std::replace_if(residual.begin(), residual.end(), predicates::const_true<int>, 0);
			residual[source_] = std::numeric_limits<int>::max();
		}
	}

	return flows;
}

Graph::~Graph()
{
}

} /* namespace algorithm */
